package binarysearch;

/**
 *
 *  本题找的是大于等于target第一个元素位置
 *
 *
 * 二分查找三种边界方式
 *
 * 1.   分别判断   nums[mid] == target  return mid;   nums[mid] < target -> l ~ mid - 1;   nums[mid] > target -> mid + 1 ~ r ； l <= r 时返回l 原因看代码方法一
 *
 * 2.   划分 [left ... right]  为  [left...mid] 和  [mid + 1...right]
 *          [left ... right]  为  [left...mid - 1] 和  [mid...right]   因为int整除向下取整  mid = (left + right) / 2 = mid会出现死循环    用mid = (left + mid + 1) / 2  参考main中的 int res3 = searchInsert_dead_loop(new int[]{1,3,5,6}, 7);
 *      这时候需要看题意  本题是查找大于target的  因此left ~ mid一定不是需要查找的区间  用第一种划分方式
 * https://leetcode-cn.com/problems/search-insert-position/solution/hua-jie-suan-fa-35-sou-suo-cha-ru-wei-zhi-by-guanp/  第一种方式
 * https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/  第二种方式
 */
public class 搜索插入位置_35 {

    /*public static int searchInsert(int[] nums, int target) {
        int l = 0, r = nums.length - 1, mid;
        while(l <= r) {
           mid = (l + r) >> 1;
           if(nums[mid] == target) {
               return mid;
           } else if(nums[mid] > target) {
               r = mid - 1;
           } else {
               l = mid + 1;
           }
        }
        //最终  只能是  l = r  - > 直接返回mid
                或者是   l + 1 = r -> r = mid - 1     此时mid = ( l + r ) / 2 整型整除向下取整 mid = l  因此 mid - 1 更新到l - 1 位置  因此l一定是对的
                 也可能是  最终位置超过数组下标  此时 l + 1 也是对的
        return l;
    }*/

    public static int searchInsert(int[] nums, int target) {
        int l = 0, r = nums.length; // {1,3,5,6}, 7 这种  相当于最后有个虚拟位置 不用减一
        // l < r 不用判断返回的是 l  还是 r  最终一定有 l = r
        // 只剩  两个数字时 只会 l + 1 = r 或者 r = l
        while(l < r) {
            int mid = (l + r) >> 1;
            if(nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        //最终l == r 随便哪个都行
        return l;
    }

    public static int searchInsert_dead_loop(int[] nums, int target) {
        int l = 0, r = nums.length - 1, mid;
        // l < r 不用判断返回的是 l  还是 r  最终一定有 l = r
        // 只剩  两个数字时 只会 l + 1 = r 或者 r = l
        while(l < r) {
            mid = (l + r) >> 1;
            if(nums[mid] < target) {
                l = mid ;
            } else {
                r = mid - 1;
            }
        }
        //最终l == r 随便哪个都行
        return l;
    }

    public static void main(String[] args) {
        // 返回l示例 1   因为最终r = -1 < l 退出了  这时返回l
        int res1 = searchInsert(new int[]{1,3,5,6}, 0);
        // 返回l示例 2   因为最终l = 4  7应该放到4 位置
        int res2 = searchInsert(new int[]{1,3,5,6}, 7);
        // 综上 返回l总是没错的

        int res3 = searchInsert_dead_loop(new int[]{1,3,5,6}, 7);

    }
}
